By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 37, Issue 2, pp. 359-670

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Range-Efficient Counting of Distinct Elements in a Massive Data Stream

A. Pavan and Srikanta Tirthapura

pp. 359-379

BibTeX  Abstract Full Text:  PDF

Derandomization in Cryptography

Boaz Barak, Shien Jin Ong, and Salil Vadhan

pp. 380-400

BibTeX  Abstract Full Text:  PDF

A $\frac32$-Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks

Gregory Mounie, Christophe Rapine, and Denis Trystram

pp. 401-412

BibTeX  Abstract Full Text:  PDF

Quantum Algorithms for the Triangle Problem

Frédéric Magniez, Miklos Santha, and Mario Szegedy

pp. 413-424

BibTeX  Abstract Full Text:  PDF

Membership Problem for the Modular Group

Yuri Gurevich and Paul Schupp

pp. 425-459

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems

A. Moss and Y. Rabani

pp. 460-481

BibTeX  Abstract Full Text:  PDF

Testing versus Estimation of Graph Properties

Eldar Fischer and Ilan Newman

pp. 482-501

BibTeX  Abstract Full Text:  PDF

Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$

Amitabha Roy and Howard Straubing

pp. 502-521

BibTeX  Abstract Full Text:  PDF

Lines and Free Line Segments Tangent to Arbitrary Three-Dimensional Convex Polyhedra

Hervé Brönnimann, Olivier Devillers, Vida Dujmović, Hazel Everett, Marc Glisse, Xavier Goaoc, Sylvain Lazard, Hyeon-Suk Na, and Sue Whitesides

pp. 522-551

BibTeX  Abstract Full Text:  PDF

One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size

Hartmut Klauck

pp. 552-583

BibTeX  Abstract Full Text:  PDF

Optimal Expected-Case Planar Point Location

Sunil Arya, Theocharis Malamatos, David M. Mount, and Ka Chun Wong

pp. 584-610

BibTeX  Abstract Full Text:  PDF

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates

Wim van Dam, Frédéric Magniez, Michele Mosca, and Miklos Santha

pp. 611-629

BibTeX  Abstract Full Text:  PDF

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems

Naveen Garg and Jochen Könemann

pp. 630-652

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for Orienteering and Discounted-Reward TSP

Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria Minkoff

pp. 653-670

BibTeX  Abstract Full Text:  PDF